package hashtable;

import java.util.HashMap;
import java.util.Map;

public class 无重复字符的最长子串_3 {
    public int lengthOfLongestSubstring(String s) {
        int left = 0, maxLen = 0; // 滑动窗口定义常见左右指针方式  显式定义一个  另一个是循环下标
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0; i < s.length(); i ++){
            Integer chooseableLeft = map.get(s.charAt(i));
            if(chooseableLeft != null){
                //  窗口只能缩减 左边界不能向左扩张
                // left > chooseableLeft + 1 时chooseableLeft + 1 才能更新为新的更大的左边界
                // 例如 ：
                // abca -> chooseableLeft = 0   -> left = 1
                //  abba  -> i = 第二个b的时候   chooseableLeft = 1  ； i=第二个a的时候  chooseableLeft = 0 , left = 1这是不对的  被历史信息干扰了  因为之前的a的最终位置还没更新
                left = Math.max(left, chooseableLeft + 1);
            }
            map.put(s.charAt(i), i);   // 更新字符的位置
            maxLen = Math.max(maxLen, i - left + 1);
        }
        return maxLen;
    }
}
